package com.example.hot100;

import com.example.tree.TreeNode;

/**
 * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
 *
 *  示例 :
 * 给定二叉树
 *
 *           1
 *          / \
 *         2   3
 *        / \
 *       4   5
 *  返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
 */
public class Leetcode543_DiameterOfBinaryTree {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        System.out.println(new Solution().diameterOfBinaryTree(root));
    }

    static class Solution {
        int res = 0;

        /**
         * 任意一条路径均可以被看作由某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到
         * 即递归向下遍历每个节点，得到每个节点的左子树深度和右子树深度之和再加一
         * 路径的长度= 经过的节点数 - 1
         * @param root
         * @return
         */
        private int dfs(TreeNode root) {
            if (root == null) return 0;
            depth(root);
            return res - 1;
        }

        private int depth(TreeNode root) {
            if (root == null) return 0;
            int leftMaxDepth = depth(root.left);
            int rightMaxDepth = depth(root.right);
            res = Math.max(res, leftMaxDepth + rightMaxDepth + 1); // 每次拿到左右子树的深度之和再加一之后，就去更新最大路径经过的节点数
            return Math.max(leftMaxDepth, rightMaxDepth) + 1;
        }

        public int diameterOfBinaryTree(TreeNode root) {
            return dfs(root);
        }
    }
}
